{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Substring with At Most K Distinct Characters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lengthOfLongestSubstringKDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #至多包含 K 个不同字符的最长子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个整数 <code>k</code> ，请你找出&nbsp;<strong>至多&nbsp;</strong>包含<em> <code>k</code></em> 个 <strong>不同</strong> 字符的最长子串，并返回该子串的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"eceba\", k = 2\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>满足题目要求的子串是 \"ece\" ，长度为 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aa\", k = 1\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>满足题目要求的子串是 \"aa\" ，长度为 2 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 50</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-substring-with-at-most-k-distinct-characters](https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-substring-with-at-most-k-distinct-characters](https://leetcode.cn/problems/longest-substring-with-at-most-k-distinct-characters/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"eceba\"\\n2', '\"aa\"\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = 0 \n",
    "        dic = {}\n",
    "        for right, val in enumerate(s):\n",
    "            dic[val] = dic.get(val, 0) + 1\n",
    "            if len(dic) > k:\n",
    "                va = s[left]\n",
    "                while len(dic) > k:\n",
    "                    va = s[left]\n",
    "                    dic[va] -= 1\n",
    "                    if dic[va] == 0:\n",
    "                        del dic[va]\n",
    "                    left += 1\n",
    "            else:\n",
    "                res = max(res, right - left + 1)\n",
    "        return res\n",
    "                   \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        mySet = set(s)\n",
    "        m, res = len(s), 0\n",
    "        l, r = 0, 1\n",
    "        while r <= m:\n",
    "            while len(set(s[l: r])) > k:\n",
    "                l += 1\n",
    "            res = max(res, len(s[l: r]))\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #贪心算法+区间搜索\n",
    "        #从左往右探索，最多k个字符串，超出的时候断开\n",
    "        #左侧移动吐出一个字符串（该字符的右侧索引最小），右侧继续探索\n",
    "        if len(s)==0 or k==0:return 0\n",
    "        d_has={}#记录当前的字符在当前选取的字符串中最右侧的index\n",
    "        l=0\n",
    "        r=0\n",
    "        l_c=s[0]#当前字串最左侧字符\n",
    "        d_has[l_c]=0\n",
    "        n=1\n",
    "        ret=\"\"\n",
    "        while l<=r and r <len(s):\n",
    "            #print(\"now:\",l,r,ret,n)\n",
    "            c=s[r]\n",
    "            if (c not in d_has or d_has[c]==-1): #可能存在c被吐出去了\n",
    "                if n==k: #如果算上当前字符，则超出了k\n",
    "                    if ret==\"\" or len(ret)<r-l:\n",
    "                        ret=s[l:r]\n",
    "                    #print(l,r,s[l:r])\n",
    "                    #左侧指针开始移动，至少要吐出一个字符\n",
    "                    l_min=d_has[s[l]]\n",
    "                    ret_before=\"\"\n",
    "                    while l<=l_min: #l指针移动，一定会存在移动到某位置时，此字符max_index=当前index\n",
    "                        # print(l,l_min,r)\n",
    "                        if d_has[s[l]]<=d_has[l_c]:\n",
    "                            l_min=d_has[s[l]]\n",
    "                        l=l+1\n",
    "                    d_has[s[l-1]]=-1 #已吐出去的字符\n",
    "                    l_c=s[l]\n",
    "                    #print(ret_before)\n",
    "                    ret=ret_before+ret #前面可能会保留部分字符\n",
    "                    #处理当前新增的这个字符信息\n",
    "                    d_has[c]=r\n",
    "                    #n=n-1+1 #左侧吐出了一个，当前新增了一个\n",
    "                else:\n",
    "                    d_has[c]=r\n",
    "                    n=n+1\n",
    "            else:\n",
    "                d_has[c]=r\n",
    "            r=r+1\n",
    "        #最后一次遍历结束的字符串，有可能也满足条件\n",
    "        if n<=k and len(ret)<r-l:\n",
    "            ret=s[l:]\n",
    "        #print (ret)\n",
    "        return len(ret)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        left = 0\n",
    "        dic = collections.defaultdict(int)\n",
    "        for right, ch in enumerate(s):\n",
    "            dic[ch] += 1\n",
    "            while len(dic) > k:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    del dic[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        tp_dict = {}\n",
    "        n = len(s)\n",
    "        l = 0\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if s[i] in tp_dict:\n",
    "                tp_dict[s[i]] = i\n",
    "            elif len(tp_dict) == k:\n",
    "                min_v = min(tp_dict.values())\n",
    "                key = [i for i, v in tp_dict.items() if v == min_v ][0]\n",
    "                del tp_dict[key]\n",
    "                tp_dict[s[i]] = i\n",
    "                l = min_v + 1\n",
    "            else:\n",
    "                tp_dict[s[i]] = i\n",
    "            res = max(i - l + 1, res)\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        count = {}\n",
    "        left = right = 0 \n",
    "\n",
    "        while right < len(s):\n",
    "            if s[right] not in count:\n",
    "                count[s[right]] = 0\n",
    "            count[s[right]] += 1\n",
    "\n",
    "            while len(count) > k:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            max_len = max(max_len, right - left + 1)\n",
    "            right += 1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        start=0\n",
    "        n=len(s)\n",
    "        hashmap=dict()\n",
    "        max_len=0\n",
    "\n",
    "        for end in range(n):\n",
    "            hashmap[s[end]]=hashmap.get(s[end],0)+1\n",
    "            if len(hashmap)<=k:\n",
    "                max_len=max(max_len,end-start+1)\n",
    "            else:\n",
    "                while len(hashmap)>k:\n",
    "                    head=s[start]\n",
    "                    hashmap[head]-=1\n",
    "                    if hashmap[head]==0:\n",
    "                        del hashmap[head]\n",
    "                    start+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0: return 0\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        max_length = k\n",
    "        sub_s = [s[i] for i in range(k)]\n",
    "        for i in range(k, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > k:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        \n",
    "        left, right = 0, 0\n",
    "        cur_dict = collections.defaultdict(int)\n",
    "        result = ''\n",
    "\n",
    "        while right < len(s):\n",
    "            char = s[right]\n",
    "            cur_dict[char] += 1\n",
    "            right += 1\n",
    "            if len(cur_dict) <= k and len(s[left:right]) > len(result):\n",
    "                result = s[left:right]\n",
    "            while len(cur_dict) > k:\n",
    "                char_to_remove = s[left]\n",
    "                cur_dict[char_to_remove] -= 1\n",
    "                if cur_dict[char_to_remove] == 0:\n",
    "                    del cur_dict[char_to_remove]\n",
    "                left +=1\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        length = len(s)\n",
    "        if (length == 0):\n",
    "            return 0\n",
    "        left = 0\n",
    "        max_len = 0\n",
    "        for i in range(length):\n",
    "            while(len(set(s[left:i+1]))>k):\n",
    "                left+=1\n",
    "            max_len = max(max_len,len((s[left:i+1])))\n",
    "        return max_len\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s, k) :\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = {}\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            # add new character and move right pointer\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains 3 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if True:\n",
    "            slow, fast = 0,0\n",
    "            cur_len, max_len = 0,0\n",
    "            while fast<len(s):\n",
    "                if len(set(s[slow:fast+1]))<=k:\n",
    "                    cur_len = fast-slow+1\n",
    "                    max_len = max(cur_len, max_len)\n",
    "                    fast +=1\n",
    "                else:\n",
    "                    slow +=1\n",
    "            return max_len\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        else:\n",
    "\n",
    "            if not isinstance(s, str):\n",
    "                return 0\n",
    "\n",
    "            def check_str(str1, k):\n",
    "                return len(set(str1))<=k\n",
    "\n",
    "            results = []\n",
    "            left, right = 0,0\n",
    "            while True:\n",
    "                if check_str(s[left:right+1], k):\n",
    "                    results.append(s[left:right+1])\n",
    "                    right +=1\n",
    "                else:\n",
    "                    left +=1\n",
    "                if right == len(s):\n",
    "                    break\n",
    "\n",
    "            results.sort(key=len, reverse=True)\n",
    "            if results:\n",
    "                return len(results[0])\n",
    "            else:\n",
    "                return 0\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "\n",
    "        window = {}\n",
    "        maxlen = float('-inf')\n",
    "        l = 0\n",
    "\n",
    "        for r in range(len(s)):\n",
    "            c = s[r]\n",
    "            window[c] = window.get(c, 0) + 1\n",
    "            while len(window) > k:\n",
    "                window[s[l]] -= 1\n",
    "                if window[s[l]] == 0:\n",
    "                    del window[s[l]]\n",
    "                l += 1\n",
    "            maxlen = max(maxlen, r -  l + 1)\n",
    "        \n",
    "        return maxlen"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Moving window. Time O(n) Space O(1)\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        window = {}\n",
    "        l, r = 0, 0\n",
    "        res = 0\n",
    "        while r < n:\n",
    "            window[s[r]] = window.get(s[r], 0) + 1\n",
    "            while len(window) > k:\n",
    "                window[s[l]] = window.get(s[l], 0) - 1\n",
    "                if window[s[l]] == 0:\n",
    "                    window.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k) -> int:\n",
    "        if not k:\n",
    "            return 0\n",
    "        left = 0\n",
    "        max_count = 0\n",
    "        record = {}\n",
    "        for i in range(len(s)):\n",
    "            record[s[i]] = i\n",
    "            if len(record)>k:\n",
    "                max_count = max(max_count, i-left)\n",
    "                left = min(record.values())+1\n",
    "                tmp = None\n",
    "                for kk in record:\n",
    "                    if record[kk] == left-1:\n",
    "                        tmp = kk\n",
    "                        break\n",
    "                record.pop(tmp)\n",
    "        max_count = max(max_count, max(record.values())-left+1)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        right = 0\n",
    "        left = 0\n",
    "        window = {}\n",
    "        non_zore = 0\n",
    "        res = 0\n",
    "\n",
    "        while right <len(s):\n",
    "            in_curr = s[right]\n",
    "            if in_curr not in window:\n",
    "                window[in_curr] = 1\n",
    "                non_zore += 1\n",
    "            else:\n",
    "                if window[in_curr] == 0:\n",
    "                    non_zore += 1\n",
    "                window[in_curr] += 1\n",
    "            right += 1\n",
    "\n",
    "            while non_zore > k:\n",
    "                out_curr = s[left]\n",
    "                window[out_curr] -= 1\n",
    "                if window[out_curr] == 0:\n",
    "                    non_zore -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #滑动窗口，左右指针，右指针的元素放到字典中，并记录字符出现的次数，循环条件，右指针不超过\n",
    "        #字符串长度，\n",
    "\n",
    "        l,r =0,0\n",
    "        res_dict={}\n",
    "        max_len=0\n",
    "\n",
    "        while r<len(s):\n",
    "            #如果s[r]已经出现过，基数加1，否则的话，初始化为1\n",
    "            res_dict[s[r]]=res_dict.get(s[r],0)+1\n",
    "            while len(res_dict)>k:\n",
    "                res_dict[s[l]]-=1\n",
    "                if res_dict[s[l]]==0:\n",
    "                    del res_dict[s[l]]\n",
    "                l+=1\n",
    "            max_len=max(max_len,r-l+1)\n",
    "            r+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0 or s=='':\n",
    "            return 0\n",
    "        slow,fast=0,0\n",
    "        longest=0\n",
    "        hashmap={}\n",
    "        window_count=0\n",
    "        distinct_count=0\n",
    "        while fast<len(s):\n",
    "            hashmap[s[fast]]=hashmap.get(s[fast],0)+1\n",
    "            while len(hashmap)>k:\n",
    "                hashmap[s[slow]]-=1\n",
    "                if hashmap[s[slow]]==0:\n",
    "                    del hashmap[s[slow]]\n",
    "                slow+=1\n",
    "            longest=max(longest,fast-slow+1)\n",
    "            fast+=1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        start = 0\n",
    "        hashmap = {}\n",
    "        \n",
    "        for end in range(len(s)):\n",
    "            tail  = s[end]\n",
    "            if tail in hashmap:\n",
    "                hashmap[tail]+=1\n",
    "            else:\n",
    "                hashmap[tail] = 1\n",
    "            if len(hashmap)<=k:\n",
    "                max_len = max(max_len,end-start+1)\n",
    "        \n",
    "            while len(hashmap)>k:\n",
    "                head = s[start]\n",
    "                hashmap[head]-=1\n",
    "                if hashmap[head]==0:\n",
    "                    del hashmap[head]\n",
    "                start+=1\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n=len(s)\n",
    "        l,mask,ans=0,[0]*300,0\n",
    "        cnt=0\n",
    "        for r in range(n):\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask[ord(s[r])-97]==1:\n",
    "                cnt+=1\n",
    "            while l<=r and cnt>k:\n",
    "                mask[ord(s[l])-97]-=1\n",
    "                if mask[ord(s[l])-97]==0: cnt-=1\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n < k+1:\n",
    "            return n\n",
    "        winfreq={}\n",
    "        for c in s:\n",
    "            winfreq[c] = 0\n",
    "        left, right = 0, 0\n",
    "        res = k\n",
    "        count = 0\n",
    "        while right < n:\n",
    "            winfreq[s[right]] += 1\n",
    "            if winfreq[s[right]] == 1:\n",
    "                count += 1\n",
    "            right += 1\n",
    "            while count == k+1:\n",
    "                winfreq[s[left]] -= 1\n",
    "                if winfreq[s[left]] == 0:\n",
    "                    count -= 1\n",
    "                left += 1\n",
    "            res = max(res, (right-left))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        start, max_length, chat_count = 0,0,{}\n",
    "\n",
    "        for end in range(len(s)):\n",
    "            chat_count[s[end]] = chat_count.get(s[end], 0) + 1\n",
    "\n",
    "            while len(chat_count) > k:\n",
    "                chat_count[s[start]] -= 1\n",
    "                if chat_count[s[start]] == 0:\n",
    "                    del chat_count[s[start]]\n",
    "                start += 1\n",
    "            \n",
    "            max_length = max(max_length, end - start +1)\n",
    "        \n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        unique_count = 0 #how many unique char\n",
    "        dic = defaultdict(int) #粗出目前每个字母的count\n",
    "\n",
    "        max_len = 0 \n",
    "\n",
    "        left , right = 0, 0 \n",
    "\n",
    "        while right <len(s):\n",
    "\n",
    "            if dic[s[right]] == 0:\n",
    "                unique_count +=1\n",
    "            dic[s[right]] +=1\n",
    "            right +=1\n",
    "\n",
    "            while unique_count>k:\n",
    "                if dic[s[left]] ==1:\n",
    "                    unique_count -=1\n",
    "                dic[s[left]] -=1\n",
    "                left +=1\n",
    "            \n",
    "            max_len= max(max_len,right-left)\n",
    "        \n",
    "        return max_len\n",
    "\n",
    "\n",
    "#         时间复杂度\n",
    "# 我们遍历了整个字符串 s，这个操作的时间复杂度是 O(len(s))。\n",
    "# 字典查找和更新操作的时间复杂度都是 O(1)。\n",
    "# 所以，总的时间复杂度是 O(len(s))。\n",
    "\n",
    "# 空间复杂度\n",
    "# 我们使用了一个额外的字典 dic 来存储每个字符出现的次数，这个字典的大小最多与 s 的长度相等。\n",
    "# 因此，总的空间复杂度是 O(len(s))。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        dic = {}\n",
    "        left = 0\n",
    "        right = 0\n",
    "        curr_max = 0\n",
    "        while right < len(s):\n",
    "            dic[s[right]] = dic.get(s[right], 0) + 1\n",
    "            while len(dic) > k:\n",
    "                dic[s[left]] -= 1\n",
    "                if dic[s[left]] == 0:\n",
    "                    dic.pop(s[left])\n",
    "                left += 1\n",
    "            curr_max = max(curr_max, right - left + 1)\n",
    "            right += 1\n",
    "        return curr_max\n",
    "            \n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        if k == 0 or not s:\n",
    "            return 0\n",
    "        \n",
    "        cnter = defaultdict(int)\n",
    "        left_idx = 0\n",
    "        right_idx = 1\n",
    "        cnter[s[left_idx]] += 1\n",
    "        ret_max = 1\n",
    "\n",
    "        while right_idx < len(s):\n",
    "            cnter[s[right_idx]] += 1\n",
    "            right_idx += 1\n",
    "            if len(cnter) <= k:\n",
    "                candidate = right_idx - left_idx\n",
    "                if candidate > ret_max:\n",
    "                    ret_max = candidate\n",
    "            else:\n",
    "                while len(cnter) > k:\n",
    "                    cnter[s[left_idx]] -= 1\n",
    "                    if cnter[s[left_idx]] == 0:\n",
    "                        cnter.pop(s[left_idx])\n",
    "                    left_idx += 1\n",
    "        \n",
    "        return ret_max\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        \n",
    "        length_of_string            = len(s)\n",
    "        hash_dict                   = collections.defaultdict(int)  # key: letter ; value: maximum position of certain letter\n",
    "        left_pointer, right_pointer = 0, -1\n",
    "        max_length                  = 0\n",
    "\n",
    "        while right_pointer+1 <= length_of_string-1:\n",
    "            \n",
    "            # 1. \n",
    "            right_pointer               += 1\n",
    "            hash_dict[s[right_pointer]] = right_pointer\n",
    "\n",
    "            # 2.\n",
    "            if len(hash_dict) == k+1:\n",
    "                minimum_position = min(hash_dict.values())\n",
    "\n",
    "                for letter, position in hash_dict.items():\n",
    "                    if position == minimum_position:\n",
    "                        minimum_position_letter = letter\n",
    "                \n",
    "                del hash_dict[minimum_position_letter]\n",
    "                left_pointer = minimum_position + 1\n",
    "\n",
    "            # 3.\n",
    "            max_length = max(max_length, right_pointer - left_pointer + 1)\n",
    "\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        n = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        left = right = 0\n",
    "        while right < n:\n",
    "            cnt[s[right]] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        \n",
    "        # left , right = 0 , 0#初始化左右指针0,0\n",
    "\n",
    "        # max_len = 0 \n",
    "\n",
    "        # #要同时记录目前为止出现了几个unique字符，和每个字符出现的次数\n",
    "        # # dic的意义在于，控制左指针是否继续往右移动。\n",
    "        # #例如eceba。 当右指针指向b，已经用了4个。此时左指针应该移动了。而e已经累计2次了，左指针目前指向e。先判断e一共出现几次，是2次，因此移动1次后还不够完全去除这个e的出现。 因此只能把出现次数减1. 此时left向右移动一次指向c，\n",
    "        # # dic = {\"e\": 1, \"c\": 1, \"b\": 1}\n",
    "        #  #由于uniuqe_count还是3>2继续移动，c只出现了一次，移除后unique_count确实-1， 也可以达到2，同时出现次数也-1，left此时移动指向e\n",
    "        #  #dic = {\"e\": 1, \"c\": 0, \"b\": 1}\n",
    "        # # 移动一次，e的次数从2 变成1，在移动一次还是不够k，在移动一次，e变成0了，这样unique_count才能顺利-1，达到只用了k个的目的\n",
    "        # unique_count =0 \n",
    "        # dic = defaultdict(int)\n",
    "\n",
    "\n",
    "        # while right < len(s):\n",
    "        #     if dic[s[right]] == 0: #如果未出现过，说明应该记录一次uniquecount\n",
    "        #         unique_count +=1\n",
    "        #     dic[s[right]] +=1 #记录此字符出现的次数\n",
    "        #     right +=1 #右指针移动\n",
    "\n",
    "        #     while unique_count > k:\n",
    "        #         if dic[s[left]] ==1: #如过\n",
    "        #             unique_count -= 1\n",
    "        #         dic[s[left]] -= 1 \n",
    "                \n",
    "        #         left += 1 \n",
    "\n",
    "                \n",
    "        #     max_len = max(max_len, right -left) #每次都更新max len\n",
    "            \n",
    "        # return max_len\n",
    "\n",
    "\n",
    "#左右指针，超过k个就移动左，\n",
    "#要用unique字母计数器， 单个字母计数器\n",
    "\n",
    "\n",
    "\n",
    "        #max lend 就是left-right\n",
    "        # 时刻控制l r 在合法范围\n",
    "        # 需要一个uniuqe count记录几个唯一字母\n",
    "\n",
    "        # 还需要记录每个字母目前出现了几次，以控制unique count的增减\n",
    "\n",
    "\n",
    "\n",
    "        left,right = 0, 0\n",
    "        max_len = 0\n",
    "        dic = defaultdict(int)#no intialize\n",
    "        unique_count = 0\n",
    "\n",
    "        while right < len(s):\n",
    "\n",
    "            if dic[s[right]] ==0: #dic默认是0 \n",
    "                unique_count +=1\n",
    "            dic[s[right]] +=1\n",
    "            right +=1\n",
    "\n",
    "            while unique_count >k: \n",
    "                if dic[s[left]]==1:\n",
    "                    unique_count -=1\n",
    "                dic[s[left]] -=1\n",
    "                left +=1\n",
    "\n",
    "            max_len = max(max_len, right -left)\\\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        hashmap = {}\n",
    "\n",
    "        wordset = set() \n",
    "\n",
    "        i = 0\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        j = 0\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        while j < len(s):\n",
    "\n",
    "            cur_char = s[j]\n",
    "            if cur_char not in hashmap:\n",
    "                hashmap[cur_char] = 1\n",
    "                count += 1\n",
    "            else:\n",
    "                hashmap[cur_char] += 1\n",
    "\n",
    "\n",
    "            while count > k:\n",
    "                cur_char = s[i]\n",
    "\n",
    "                if cur_char in hashmap:\n",
    "                    hashmap[cur_char] -= 1\n",
    "                    if hashmap[cur_char] == 0:\n",
    "                        del hashmap[cur_char]\n",
    "                        count -= 1\n",
    "                    \n",
    "                i += 1\n",
    "\n",
    "            res = max(res, j - i + 1)\n",
    "\n",
    "            j += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0:\n",
    "            return 0\n",
    "        start = 0\n",
    "        max_len = 0\n",
    "        h = dict()\n",
    "        count_set=set()\n",
    "        length = list()\n",
    "        for n in range(len(s)):\n",
    "            h[s[n]] = h.get(s[n],0)+1\n",
    "            if  len(h)<=k:\n",
    "                max_len= max(n-start+1, max_len)\n",
    "            while len(h)>k:\n",
    "                h[s[start]] -= 1\n",
    "                if h.get(s[start])==0:\n",
    "                    del  h[s[start]]\n",
    "                start += 1               \n",
    "        return max_len        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        d, res, l = defaultdict(int), 0, 0\n",
    "        for r, c in enumerate(s):\n",
    "            d[c] += 1\n",
    "            while len(d) > k:\n",
    "                d[s[l]] -= 1\n",
    "                if d[s[l]] == 0:\n",
    "                    d.pop(s[l])\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > k:\n",
    "                left_c = s[left]\n",
    "                cache[left_c] -= 1\n",
    "                if not cache[left_c]:\n",
    "                    del cache[left_c]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left,right=0,0\n",
    "        used=dict()\n",
    "        if k==0:\n",
    "            return 0\n",
    "        max_lenth=0\n",
    "        while right<len(s):\n",
    "            if s[right] in used:\n",
    "                used[s[right]]=right\n",
    "                right+=1\n",
    "                max_lenth=max(max_lenth,right-left)\n",
    "            elif s[right] not in used:\n",
    "                if len(used)<k:\n",
    "                    used[s[right]]=right\n",
    "                    right+=1\n",
    "                    max_lenth=max(max_lenth,right-left)\n",
    "                else:\n",
    "                    min_key=None\n",
    "                    min_index=1000000\n",
    "                    for key,val in used.items():\n",
    "                        if val<min_index:\n",
    "                            min_key=key\n",
    "                            min_index=val\n",
    "                    left=min_index+1\n",
    "                    used.pop(min_key)\n",
    "                    used[s[right]]=right\n",
    "                    right+=1\n",
    "                    max_lenth=max(max_lenth,right-left)\n",
    "        \n",
    "        return max_lenth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        l = 0\n",
    "        ans = 0\n",
    "        for r,x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[l]] -= 1\n",
    "                if not cnt[s[l]]:\n",
    "                    cnt.pop(s[l])\n",
    "                l += 1\n",
    "            ans = max(ans,r - l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        max_len = 0\n",
    "        d = {}\n",
    "        start = 0\n",
    "        for end in range(len(s)):\n",
    "            tail = s[end]\n",
    "            if tail in d:\n",
    "                d[tail]+=1\n",
    "            else:\n",
    "                d[tail]=1\n",
    "            if len(d)<=k:\n",
    "                max_len = max(max_len,end-start+1)\n",
    "            while len(d)>k:\n",
    "                head = s[start]\n",
    "                d[head] -= 1\n",
    "                if d[head] == 0:\n",
    "                    del d[head]\n",
    "                start+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        ### solution\n",
    "        # sliding window + hash\n",
    "        # sliding window + ordereddict\n",
    "\n",
    "        ## sw + ordereddict\n",
    "        n = len(s)\n",
    "        i = j = 0\n",
    "        res = 0\n",
    "        od = collections.OrderedDict()\n",
    "        numCha = 0\n",
    "        while j < n:\n",
    "            if s[j] in od:\n",
    "                del od[s[j]]\n",
    "            od[s[j]] = j\n",
    "            if len(od) > k:\n",
    "                c, idx = od.popitem(last=False)\n",
    "                i = idx + 1\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res\n",
    "\n",
    "        ## sw + hash\n",
    "        n = len(s)\n",
    "        i = j = 0\n",
    "        res = 0\n",
    "        cnt = collections.Counter()\n",
    "        numCha = 0\n",
    "        while j < n:\n",
    "            cnt[s[j]] += 1\n",
    "            if cnt[s[j]] == 1:\n",
    "                numCha += 1\n",
    "            while numCha > k and i <= j:\n",
    "                cnt[s[i]] -= 1\n",
    "                if cnt[s[i]] == 0:\n",
    "                    numCha -= 1\n",
    "                i += 1\n",
    "            res = max(res, j - i + 1)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        cnt = Counter()\n",
    "        left = right = 0\n",
    "        n = len(s)\n",
    "        # [left, right]: the longest\n",
    "        res = 0\n",
    "        while right < n:\n",
    "            cnt[s[right]] += 1\n",
    "\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        dic = {}\n",
    "        l, r = 0, 0\n",
    "        length = 0\n",
    "        n = len(s)\n",
    "        while r<n:\n",
    "            dic[s[r]] = r\n",
    "            while len(dic)>k:\n",
    "                if s[l] in dic and dic[s[l]]==l:\n",
    "                    del dic[s[l]]\n",
    "                l+=1\n",
    "            r+=1\n",
    "            if r-l>length:\n",
    "                length =r-l\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        n = len(s)\n",
    "        cache = {}\n",
    "        left = 0\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            cache[c] = cache.get(c, 0) + 1\n",
    "            while len(cache) > k:\n",
    "                cache[s[left]] -= 1\n",
    "                if cache[s[left]] == 0:\n",
    "                    del cache[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, i - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        count = defaultdict(int)\n",
    "        left = right = 0\n",
    "        res = 0\n",
    "        while right < len(s):\n",
    "            count[s[right]] += 1\n",
    "            while len(count) > k:\n",
    "                count[s[left]] -= 1\n",
    "                if count[s[left]] == 0:\n",
    "                    del count[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "            right += 1\n",
    "            \n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        s_len = len(s)\n",
    "\n",
    "        if s_len < k:\n",
    "            return s_len\n",
    "\n",
    "        left = right = 0\n",
    "\n",
    "        result = float(\"-inf\")\n",
    "        storage = {}\n",
    "\n",
    "        while right < s_len:\n",
    "            storage[s[right]] = right\n",
    "\n",
    "            right += 1\n",
    "\n",
    "            if len(storage) > k:\n",
    "                del_index = min(storage.values())\n",
    "                del storage[s[del_index]]\n",
    "                left = del_index + 1\n",
    "            result = max(result, right - left)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "            ##s = \"eceba\", k = 2， left和right先同时指向第一个e\n",
    "             #   2 指针的思想其实是 \n",
    "            dic = defaultdict(int)  # 用于记录每个字符的出现次数|如果没有key，默认返回0 \n",
    "            left = 0  # 窗口的左边界\n",
    "            right = 0  # 窗口的右边界，从第一位开始\n",
    "            max_len = 0  # 累计记录max len，跟209对比，那个题求min，所以初始化为一个inf。此处求max，就初始化小一点\n",
    "            counter = 0  # 记录distinct字符的数量,我们最多只能有k个，如果超过了，说明left要往右移\n",
    "             #1. \n",
    "            while right < len(s):#右边界不能超过字符串长度,right从0位开始，也就是e\n",
    "                if dic[s[right]] == 0:  # 如果这个字符没在字典里，确实返回0，lookup存的是每个字符出现的次数\n",
    "                    counter += 1  # 那么distinct字符的count加1\n",
    "                dic[s[right]] += 1  # 更新这个字符的出现次数--key value |\n",
    "                #1：dic = {\"e\": 1} 2： \n",
    "                right += 1  # 扩大窗口的右边界\n",
    "\n",
    "           #2.限制条件     # 当distinct的字符数量超过了k说明多了，那么left要往右移动了，【直到】只剩下2个不同字符\n",
    "                while counter > k:  # 如果窗口中不同字符的数量超过k，\n",
    "                    if dic[s[left]] == 1:  # 如果这个字符只出现了一次,那么移动左指针的话，counter里面也会少一个。如果出现n次就直接下一步-1即可，但counter里面unique字符数不会变\n",
    "                        counter -= 1  # 不同字符的数量减1\n",
    "                    dic[s[left]] -= 1  # 先让dic里面计数减掉\n",
    "                    left += 1  # 再移动left向右\n",
    "            # 3.maxlen  不论怎样都做  #只有distinct字符<=2个，我们才会算当前max多长，前面这个counter的while就是避免这个情况\n",
    "                max_len = max(max_len, right - left)  # 更新窗口的最大大小，由于用的max，他只会变多\n",
    "\n",
    "            return max_len #要的就是max\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left_index=0\n",
    "        right_index=0\n",
    "        max_lens=0\n",
    "        child_string=\"\"\n",
    "        for index in range(len(s)):\n",
    "            child_string=child_string+s[index]\n",
    "            while(len(set(child_string))>k):\n",
    "                child_string=s[left_index:right_index+1]\n",
    "                left_index+=1\n",
    "            if len(child_string)>max_lens:\n",
    "                max_lens=len(child_string)\n",
    "            right_index+=1\n",
    "        return max_lens"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        counter = collections.Counter()\n",
    "        result = left = right = 0\n",
    "        while right < n:\n",
    "            while right < n and len(counter) <= k:\n",
    "                counter[s[right]] += 1\n",
    "                right += 1\n",
    "            # print(right, left)\n",
    "            if len(counter) <= k:\n",
    "                result = max(result, right - left)\n",
    "            else:\n",
    "                result = max(result, right - left - 1)\n",
    "            counter[s[left]] -= 1\n",
    "            if not counter[s[left]]:\n",
    "                counter.pop(s[left])\n",
    "            left += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        left = 0\n",
    "        visited = {}\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        for i in range(len(s)):\n",
    "            visited.setdefault(s[i],0)\n",
    "            if visited[s[i]] == 0:\n",
    "                cnt += 1 \n",
    "            visited[s[i]] += 1\n",
    "            while cnt > k and left < i:\n",
    "                visited[s[left]] -= 1\n",
    "                if visited[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "\n",
    "            #print(left,i,visited,cnt)\n",
    "            res = max(res,i - left + 1)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: 'str', k: 'int') -> 'int':\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = defaultdict()\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            # add new character and move right pointer\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains 3 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        left, right = 0, 0\n",
    "        ans = 0\n",
    "        \n",
    "        while right < n:\n",
    "            temp = s[left:right+1]\n",
    "            if len(set(temp)) <= k:\n",
    "                ans = max(ans, len(temp))\n",
    "            else:\n",
    "                left += 1\n",
    "            right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        low = 0\n",
    "        max_len = 0\n",
    "        tmp = dict()\n",
    "        for fast in range(len(s)):\n",
    "            tmp[s[fast]] = tmp.get(s[fast],0) + 1\n",
    "            if len(tmp) <= k:\n",
    "                max_len = max(max_len, fast-low+1)\n",
    "            while len(tmp) > k: # 若窗口长度大于字典长度，说明有重复元素，此时应该减少该元素\n",
    "                head = s[low]\n",
    "                tmp[head] -= 1\n",
    "                if tmp[head] == 0:\n",
    "                    del tmp[head]\n",
    "                low += 1\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        window_dict = {}\n",
    "        for i in s:\n",
    "            window_dict[i] = 0\n",
    "\n",
    "\n",
    "        right = 0\n",
    "        left = 0\n",
    "        res = 0\n",
    "        count = 0\n",
    "\n",
    "        while right < len(s):\n",
    "            right_char = s[right]\n",
    "            right += 1\n",
    "\n",
    "            if window_dict[right_char] == 0:\n",
    "                count += 1\n",
    "\n",
    "            window_dict[right_char] += 1\n",
    "\n",
    "            if count <= k:\n",
    "                res = max(res, right - left)\n",
    "\n",
    "            while count > k:\n",
    "                left_char = s[left]\n",
    "                left += 1\n",
    "\n",
    "                if window_dict[left_char] == 1:\n",
    "                    count -= 1\n",
    "\n",
    "                window_dict[left_char] -= 1\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        hs = {}\n",
    "        if k == 0:return 0\n",
    "\n",
    "        hs[s[0]] = 1\n",
    "        ss = 0\n",
    "        ee = 1\n",
    "        res = 1\n",
    "        while ee < len(s):\n",
    "            if s[ee] in hs:\n",
    "                hs[s[ee]] +=1\n",
    "            else:\n",
    "                hs[s[ee]] = 1\n",
    "\n",
    "            if len(hs) >k:\n",
    "                while ss < ee and len(hs) >k:\n",
    "                    if hs[s[ss]] == 1:\n",
    "                        del hs[s[ss]]\n",
    "                    else:\n",
    "                        hs[s[ss]] -=1\n",
    "                    ss +=1\n",
    "            \n",
    "            res = max(res, ee-ss+1)\n",
    "\n",
    "            ee+=1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        l = r = 0\n",
    "        d = dict()\n",
    "        ans = 0\n",
    "        while r < len(s):\n",
    "            if s[r] not in d:\n",
    "                d[s[r]] = 1\n",
    "            else:\n",
    "                d[s[r]] += 1\n",
    "            while len(d.keys()) > k:\n",
    "                if d[s[l]] == 1:\n",
    "                    del d[s[l]]\n",
    "                else:\n",
    "                    d[s[l]] -= 1\n",
    "                l += 1\n",
    "            r += 1\n",
    "            ans = max(ans,r-l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if len(s) == 0:\n",
    "            return 0\n",
    "\n",
    "        p, q = 1, 0\n",
    "\n",
    "        char_dict = defaultdict(int)\n",
    "        # char_dict[s[0]] = 1\n",
    "        max_len = 0\n",
    "        \n",
    "        while p<= len(s):\n",
    "            c = s[p-1]\n",
    "            char_dict[c] +=1\n",
    "            while len(char_dict) > k:\n",
    "                c2rmv = s[q]\n",
    "                char_dict[c2rmv] -=1\n",
    "                if char_dict[c2rmv] == 0:\n",
    "                    del char_dict[c2rmv]\n",
    "                q+=1\n",
    "            max_len = max(p-q, max_len)\n",
    "            p+=1\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        from collections import Counter\n",
    "        left,res =0,0\n",
    "        cnt = Counter()\n",
    "        for right,c in enumerate(s):\n",
    "            cnt[c]+=1\n",
    "            while len(cnt)>k:\n",
    "                cnt[s[left]]-=1\n",
    "                if cnt[s[left]]==0:\n",
    "                    del cnt[s[left]]\n",
    "                left+=1\n",
    "            res=max(res,right-left+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        record = {}\n",
    "        slow = 0\n",
    "        max_len = 0\n",
    "        for fast in range(len(s)):\n",
    "            if s[fast] in record:\n",
    "                record[s[fast]] += 1\n",
    "            else:\n",
    "                record[s[fast]] = 1\n",
    "                while len(record) == k + 1:\n",
    "                    record[s[slow]] -= 1\n",
    "                    if record[s[slow]] == 0:\n",
    "                        record.pop(s[slow])\n",
    "                    slow += 1\n",
    "            max_len = max(max_len, fast - slow + 1)\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0: return 0\n",
    "        if len(s) <= k:\n",
    "            return len(s)\n",
    "        max_length = k\n",
    "        sub_s = [s[i] for i in range(k)]\n",
    "        for i in range(k, len(s)):\n",
    "            sub_s.append(s[i])\n",
    "            set_sub_s = set(sub_s)\n",
    "            if len(set_sub_s) > k:\n",
    "                sub_s.pop(0)\n",
    "            elif len(sub_s) >= max_length:\n",
    "                max_length = len(sub_s)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        l, r = 0, 0\n",
    "        cnt = defaultdict(int)\n",
    "        ans = 0\n",
    "        while r < len(s):\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[l]] -= 1\n",
    "                if cnt[s[l]] == 0:\n",
    "                    del cnt[s[l]]\n",
    "                l += 1\n",
    "            print(l, r)\n",
    "            while r < len(s) and len(cnt) <= k:\n",
    "                ans = max(ans, r - l)\n",
    "                cnt[s[r]] += 1\n",
    "                r += 1\n",
    "            if len(cnt) <= k:\n",
    "                ans = max(ans, r - l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        left = 0\n",
    "        right = 0\n",
    "        cnt = Counter()\n",
    "        for right, x in enumerate(s):\n",
    "            cnt[x] += 1\n",
    "            while len(cnt) > k:\n",
    "                cnt[s[left]] -= 1\n",
    "                if cnt[s[left]] == 0:\n",
    "                    del cnt[s[left]]\n",
    "                left += 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        ret=1\n",
    "        l=0\n",
    "        if k==0: return 0\n",
    "        p=collections.defaultdict(str)\n",
    "        p[s[0]]=1\n",
    "        for r in range(1,len(s)):\n",
    "            if len(p)<k:\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            elif s[r] in p:\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            else:\n",
    "                while(len(p)>=k):\n",
    "                    if p[s[l]]: p[s[l]]-=1\n",
    "                    if not p[s[l]]:\n",
    "                        p.pop(s[l])\n",
    "                    l+=1\n",
    "                p[s[r]]=p.get(s[r],0)+1\n",
    "            ret=max(ret,r-l+1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        mySet = set(s)\n",
    "        m, res = len(s), 0\n",
    "        l, r = 0, 1\n",
    "        while r <= m:\n",
    "            while len(set(s[l: r])) > k:\n",
    "                l += 1\n",
    "            res = max(res, len(s[l: r]))\n",
    "            r += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        if n == 0 or k == 0:\n",
    "            return 0\n",
    "        left, right = 0, 0\n",
    "        max_len = 1\n",
    "        count = collections.defaultdict(int)\n",
    "        while right < n:\n",
    "            count[s[right]] = right\n",
    "            if len(count) == (k + 1):\n",
    "                index = min(count.values())\n",
    "                del count[s[index]]\n",
    "                left = index + 1\n",
    "            max_len = max(max_len, right - left + 1)\n",
    "            right += 1\n",
    "        return max_len\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        left = 0\n",
    "        res = 0\n",
    "        my_set = defaultdict(int)\n",
    "        for right in range(n):\n",
    "            my_set[s[right]] += 1\n",
    "            if len(my_set.keys()) <= k:\n",
    "                res = max(res, right - left + 1)\n",
    "            while len(my_set.keys()) > k:\n",
    "                my_set[s[left]] -= 1\n",
    "                if my_set[s[left]] == 0:\n",
    "                    del my_set[s[left]]\n",
    "                left += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left, right, cnt, res = 0, 0, 0, 0\n",
    "        m = defaultdict(int)\n",
    "        while right < len(s):\n",
    "            m[s[right]] += 1\n",
    "            if m[s[right]] == 1:\n",
    "                cnt += 1\n",
    "            right += 1\n",
    "            while left < right and cnt > k:\n",
    "                m[s[left]] -= 1\n",
    "                if m[s[left]] == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            res = max(res, right - left)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        #简单计数+滑窗即可\n",
    "        n=len(s)\n",
    "        l,mask,ans=0,[0]*300,0\n",
    "        cnt=0\n",
    "        for r in range(n):\n",
    "            mask[ord(s[r])-97]+=1\n",
    "            if mask[ord(s[r])-97]==1:\n",
    "                cnt+=1\n",
    "            while l<=r and cnt>k:\n",
    "                mask[ord(s[l])-97]-=1\n",
    "                if mask[ord(s[l])-97]==0: cnt-=1\n",
    "                l+=1\n",
    "            ans=max(ans,r-l+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        from collections import OrderedDict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: 'str', k: 'int') -> 'int':\n",
    "        n = len(s) \n",
    "        if k == 0 or n == 0:\n",
    "            return 0\n",
    "        \n",
    "        # sliding window left and right pointers\n",
    "        left, right = 0, 0\n",
    "        # hashmap character -> its rightmost position \n",
    "        # in the sliding window\n",
    "        hashmap = OrderedDict()\n",
    "\n",
    "        max_len = 1\n",
    "        \n",
    "        while right < n:\n",
    "            character = s[right]\n",
    "            # if character is already in the hashmap -\n",
    "            # delete it, so that after insert it becomes\n",
    "            # the rightmost element in the hashmap\n",
    "            if character in hashmap:\n",
    "                del hashmap[character]\n",
    "            hashmap[character] = right\n",
    "            right += 1\n",
    "\n",
    "            # slidewindow contains k + 1 characters\n",
    "            if len(hashmap) == k + 1:\n",
    "                # delete the leftmost character\n",
    "                _, del_idx = hashmap.popitem(last = False)\n",
    "                # move left pointer of the slidewindow\n",
    "                left = del_idx + 1\n",
    "\n",
    "            max_len = max(max_len, right - left)\n",
    "\n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        l, r = 0, 0\n",
    "        has = {}\n",
    "        res = 0\n",
    "        for r in range(n):\n",
    "\n",
    "            has[s[r]] = has.get(s[r], 0) + 1\n",
    "\n",
    "            while len(has) > k:\n",
    "\n",
    "                has[s[l]] -= 1\n",
    "                if has[s[l]] == 0:\n",
    "                    del has[s[l]]\n",
    "                l += 1\n",
    "            res = max(res, r - l + 1)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        window = defaultdict(int)\n",
    "\n",
    "        res = 0\n",
    "        left, right = 0, 0\n",
    "        while right < len(s):\n",
    "            c = s[right]\n",
    "            right += 1\n",
    "\n",
    "            window[c] += 1\n",
    "\n",
    "            while len(window) > k:\n",
    "                d = s[left]\n",
    "                left += 1\n",
    "                window[d] -= 1\n",
    "                if window[d] == 0:\n",
    "                    window.pop(d)\n",
    "            \n",
    "            res = max(res, right - left)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        visited = collections.defaultdict(int)\n",
    "        l, r = 0, 0\n",
    "        max_len = 0\n",
    "        for r in range(len(s)):\n",
    "            visited[s[r]] += 1\n",
    "            while l < r and len(visited) > k:\n",
    "                if visited[s[l]] == 1:\n",
    "                    del visited[s[l]]\n",
    "                else:\n",
    "                    visited[s[l]] -= 1\n",
    "                l += 1\n",
    "            if r - l + 1 > max_len:\n",
    "                max_len = r - l + 1\n",
    "        \n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left = 0\n",
    "        window = defaultdict(lambda: 0)\n",
    "        type_cnt = 0\n",
    "\n",
    "        res = 0\n",
    "        for right, c in enumerate(s):\n",
    "            window[c] += 1\n",
    "            if window[c] == 1:\n",
    "                type_cnt += 1\n",
    "\n",
    "            while type_cnt> k:\n",
    "                d = s[left]\n",
    "                window[d] -= 1\n",
    "                left += 1\n",
    "\n",
    "                if window[d] == 0:\n",
    "                    type_cnt -= 1\n",
    "            res = max(res, right - left + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "substring内最多就k个不同的char\n",
    "但是个数小于k也行\n",
    "\"\"\"\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:        \n",
    "        char_to_freq = Counter()\n",
    "        left = 0\n",
    "        res = 0\n",
    "\n",
    "        for right in range(len(s)):\n",
    "            char_to_freq[s[right]] += 1\n",
    "\n",
    "            # window最多只能有k个不同char, 如果个数大于k,就要shrink\n",
    "            while len(char_to_freq) > k:\n",
    "                char_to_freq[s[left]] -= 1\n",
    "                if char_to_freq[s[left]] == 0:\n",
    "                    del char_to_freq[s[left]]\n",
    "                left += 1\n",
    "            \n",
    "            res = max(res, right - left + 1)\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        left = ans = 0\n",
    "        meepo = dict()\n",
    "        n = len(s)\n",
    "\n",
    "        for right, ch in enumerate(s):\n",
    "            meepo[ch] = meepo.get(ch, 0) + 1\n",
    "\n",
    "            if len(meepo) > k:        # now, right is actually right + 1\n",
    "                ans = max(ans, right - left) \n",
    "\n",
    "                while len(meepo) > k:       # delete untill there is k distinct chs\n",
    "                    left_ch = s[left]\n",
    "                    meepo[left_ch] -= 1\n",
    "                    if meepo[left_ch] == 0:      # delete empty ch = len(meepo) - 1\n",
    "                        del meepo[left_ch]\n",
    "                    left += 1\n",
    "\n",
    "        # update for the last ch, where right = n-1, length = right-left-1:\n",
    "        ans = max(ans, right - left + 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "\n",
    "        l,r =0,0\n",
    "        res_dict={}\n",
    "        max_len=0\n",
    "\n",
    "        while r<len(s):\n",
    "            res_dict[s[r]]=res_dict.get(s[r],0)+1\n",
    "            while len(res_dict)>k:\n",
    "                res_dict[s[l]]-=1\n",
    "                if res_dict[s[l]]==0:\n",
    "                    del res_dict[s[l]]\n",
    "                l+=1\n",
    "            max_len=max(max_len,r-l+1)\n",
    "            r+=1\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k==0 or s=='':\n",
    "            return 0\n",
    "        slow,fast=0,0\n",
    "        longest=0\n",
    "        hashmap={}\n",
    "        window_count=0\n",
    "        distinct_count=0\n",
    "        while fast<len(s):\n",
    "            hashmap[s[fast]]=hashmap.get(s[fast],0)+1\n",
    "            while len(hashmap)>k:\n",
    "                hashmap[s[slow]]-=1\n",
    "                if hashmap[s[slow]]==0:\n",
    "                    del hashmap[s[slow]]\n",
    "                slow+=1\n",
    "            # if len(hashmap)==k:\n",
    "            longest=max(longest,fast-slow+1)\n",
    "            fast+=1\n",
    "        return longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "\n",
    "        n = len(s)\n",
    "        if n < k + 1:\n",
    "            return n\n",
    " \n",
    "        # 滑动窗口的左右指针\n",
    "        left, right = 0, 0\n",
    "        # hashmap 中的字符 -> 它在滑动窗口中最靠右的位置\n",
    "        hashmap = defaultdict()\n",
    " \n",
    "        max_len = k\n",
    " \n",
    "        while right < n:\n",
    "            # 当滑动窗口包含小于 3 个字符\n",
    "            hashmap[s[right]] = right\n",
    "            right += 1\n",
    " \n",
    "            # 滑动窗口包含 3 个字符\n",
    "            if len(hashmap) == k + 1:\n",
    "                # 删除最左边的字符\n",
    "                del_idx = min(hashmap.values())\n",
    "                del hashmap[s[del_idx]]\n",
    "                # 删除滑动窗口的左指针\n",
    "                left = del_idx + 1\n",
    " \n",
    "            max_len = max(max_len, right - left)\n",
    " \n",
    "        return max_len\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        maps = collections.defaultdict(int)\n",
    "        n = len(s)\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        res = 0\n",
    "        l = r = 0\n",
    "        while r < n:\n",
    "            maps[s[r]] += 1\n",
    "            while len(maps) > k:\n",
    "                maps[s[l]] -= 1\n",
    "                if maps[s[l]] == 0:\n",
    "                    del maps[s[l]]\n",
    "                l += 1\n",
    "            \n",
    "            res = max(res, r-l+1)\n",
    "            r+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "        if k == 0:\n",
    "            return 0\n",
    "        max_length = 0\n",
    "        left = 0\n",
    "        dic = dict()\n",
    "        sett = set()\n",
    "        for right in range(len(s)):\n",
    "            if s[right] in sett:\n",
    "                dic[s[right]] += 1\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "            else:\n",
    "                while left < right and len(sett) == k:\n",
    "                    left_char = s[left]\n",
    "                    dic[left_char] -= 1\n",
    "                    if dic[left_char] == 0:\n",
    "                        del dic[left_char]\n",
    "                        sett.remove(left_char)\n",
    "                    left += 1\n",
    "                dic[s[right]] = 1\n",
    "                sett.add(s[right])\n",
    "                max_length = max(max_length, right - left + 1)\n",
    "        return max_length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:\n",
    "      n = len(s)\n",
    "      i = j = 0\n",
    "      res = 0\n",
    "      cnt = collections.Counter() # 计数哈希\n",
    "      numCha = 0 # 窗口里的不同字符的数量\n",
    "      while j < n:\n",
    "          cnt[s[j]] += 1\n",
    "          if cnt[s[j]] == 1: # 有新的字符加入\n",
    "              numCha += 1\n",
    "          while numCha > k and i <= j:\n",
    "              cnt[s[i]] -= 1\n",
    "              if cnt[s[i]] == 0: # 有字符被移除窗口\n",
    "                  del cnt[s[i]] # 也可以不用删除\n",
    "                  numCha -= 1\n",
    "              i += 1\n",
    "          res = max(res, j - i + 1)\n",
    "          j += 1\n",
    "      return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
